package Real19;


/**
 * 类似于fbnq的数列的累加是及其夸张的，比如1 1 2···，在fbnq(47)时int就已经溢出了,不到70w时 double就溢出了；  这种给个2000w的就压根离谱，明显是阻止硬算的；
 * 只关心后几位的话，就不需要对更高位进行运算或保存了，决定后几位的永远是后几位，在加减完成后高位的进位不影响后几位是谁，所以把进位扔掉就好了；
 * @author lenovo
 *
 */
public class Main2 {
	
	public static void main(String[] args) {
		
		int[] memo = new int[20190325]; //+1
		
		System.out.println(fbnqx(20190324,memo));  //使用的是dp，自底向上。所以memo也可以在fbnq函数里创建，因为不会递归调用导致反复创建；

	}

	private static int fbnqx(int i, int[] memo) {

//		if( i < 4)
//			return 1; 

		int flag = 1;
		while(flag <= 3) {
			memo[flag] = 1;
			flag++;
		}
		
		for( int j = 4; j <= i; j++) {
			memo[j] = ( memo[j-1] + (memo[j-2]) + (memo[j-3]) ) %10000 ;
		}
		
		return memo[i];
	}

}
